The present invention relates to optimizing queries, and in particular, to rewriting join queries to access data through a view or from a materialized view.
In a database management system (DBMS), data is stored in one or more data containers, each container contains records, and the data within each record is organized into one or more fields. In relational database systems, the data containers are referred to as tables, the records are referred to as rows, and the fields are referred to as columns. In object oriented databases, the data containers are referred to as object classes, the records are referred to as objects, and the fields are referred to as attributes. Other database architectures may use other terminology.
The present invention is not limited to any particular type of data container or database architecture. However, for the purpose of explanation, the examples and the terminology used herein shall be that typically associated with relational databases. Thus, the terms xe2x80x9ctablexe2x80x9d, xe2x80x9crowxe2x80x9d and xe2x80x9ccolumnxe2x80x9d shall be used herein to refer respectively to the data container, record, and field.
For various reasons, it is not desirable for certain users to have access to all of the columns of a table. For example, one column of an employee table may hold the salaries for the employees. Under these circumstances, it may be desirable to limit access to the salary column to management, and allow all employees to have access to the other columns. To address this situation, the employees may be restricted from directly accessing the table. Instead, they may be allowed to indirectly access the appropriate columns in the table through a xe2x80x9cviewxe2x80x9d.
A view is a logical table. As logical tables, views may be queried by users as if they were a table. However, views actually present data that is extracted or derived from existing tables. Thus, the problem described above may be solved by (1) creating a view that extracts data from all columns of the employee table except the salary column, and (2) allowing all employees to access the view.
The data presented by conventional views is gathered and derived on-the-fly from the base tables in response to queries that access the views. The data gathered for the view is not persistently stored after the query accessing the view has been processed. Because the data provided by conventional views is gathered from the base tables at the time the views are accessed, the data from the views will reflect the current state of the base tables. However, the overhead associated with gathering the data from the base tables for a view every time the view is accessed may be prohibitive.
A materialized view, on the other hand, is a view for which a copy of the view data is stored separate form the base tables from which the data was originally gathered and derived. The data contained in a materialized view is referred to herein as xe2x80x9cmaterialized dataxe2x80x9d. Materialized views eliminate the overhead associated with gathering and deriving the view data every time a query accesses the view.
However, to provide the proper data, materialized views must be maintained to reflect the current state of the base tables. When the base tables of a materialized view are modified, computer resources must be expended to both determine whether the modifications require corresponding changes to the materialized data, and to make the required corresponding changes. Despite the high cost associated with maintaining materialized views, using a materialized view can lead to significant overall cost savings relative to a conventional view when the materialized view represents a set of data that is infrequently changed but frequently accessed.
A view is defined by metadata referred to as a view definition. The view definition contains mappings to one or more columns in the one or more tables containing the data. Columns and tables that are mapped to a view are referred to herein as base columns and base tables of the view, respectively.
Typically, the view definition is in the form of a database query. These queries, like any database query, must conform to the rules of a particular query language such as the ANSI Structured Query Language (SQL). For example, the query:
SELECT T.a FROM T WHERE T.b=1
retrieves column T.a of table T for those rows whose value in T.b equals 1. The above query includes a SELECT clause (i.e. xe2x80x9cSELECT T.axe2x80x9d), a FROM clause (i.e. xe2x80x9cFROM Txe2x80x9d), and a WHERE clause (i.e. xe2x80x9cT.b=1xe2x80x9d). The FROM clause specifies one or more tables or views from which to retrieve values. The tables or views are referred to as the FROM list. The SELECT clause specifies one or more columns in the items in the FROM list from which to retrieve values. The one or more columns are referred to as the SELECT list. The WHERE clause specifies the rows from which the values are retrieved. Specifically, the WHERE clause contains one or more logical expressions defining criteria that must be meet by the rows from which values are retrieved.
Views are often based on joins of two or more tables. A join is an operation that combines rows from two or more tables and views that meet a condition.
FIG. 1 shows tables that are used to illustrate a join. FIG. 1 shows tables X 190, Y 170, and Z 180. Materialized view YZ 110 represents the results of an xe2x80x9cequijoinxe2x80x9d between tables Y 170 and Z 180. An equijoin is a particular type of join where a row from a first table is combined with one or more rows from a second table, if the value in a specified column from the first table equals a value in a specified column from the second table. For example, combining the rows from table Y 170 and table Z 180 using the join condition y.a=z.a produces materialized view YZ 110. In materialized view YZ 110, row 114 was formed by combining row 172 (i.e. columns y.a and y.b in row 114) and 182 (i.e. columns z.a and z.b in row 114) because for rows 172 and 182, the value in y.a equals the valve in z.a. Because the logical expression y.a=z.a is based on columns from the joined tables, it is referred to as a join condition.
A join is performed whenever a join is specified by a query. As a matter of convenience, the value in a column of a row may be referred to by the label or name of the column. For example, the expression xe2x80x9cvalue in y.a equals the value in z.axe2x80x9d may be expressed as xe2x80x9cy.a equals z.axe2x80x9d, or xe2x80x9cy.a=z.axe2x80x9d.
A join may be specified by a query by including the tables to be joined in the FROM list and including a logical expression specifying the needed conditions in the WHERE clause. For example, the previous equijoin of tables Y 170 and Z 180 may be specified by a query as follows:
SELECT*FROM Y, Z WHERE y.a=z.a
In addition to join conditions, the WHERE clause of a join query can also contain other conditions that refer to columns of only one table. These conditions can further restrict the rows returned by the join query.
Generating joins in response to receiving join queries can require a substantial amount of processing. To reduce the amount of such processing, a database manager transforms join queries to retrieve data from the xe2x80x9cpreprocessedxe2x80x9d materialized data residing in a materialized view. Currently, database systems that include query rewrite mechanisms rewrite some types of join queries but not other types of join queries.
An example of a query not transformed under the conventional approach is a query based on an antijoin of tables. Let W|-p(w,t)T denote a antijoin between tables W and T on condition p(w,t). A antijoin results in another table that consists of the rows in W where condition p(w,t) evaluates to FALSE. If the condition is not relevant, a shorter notation W|-T is used to represent the antijoin. The first table W is referred to as the xe2x80x9cleftxe2x80x9d table, and the second table T as the xe2x80x9crightxe2x80x9d table with respect to the antijoin. Typically, the condition of an antijoin requires that a column from the left table match the value of a column in the right table. Structures shown in FIG. 2 are used as an example to illustrate an antijoin.
FIG. 2 shows table W 270 and T 280 and antijoin table 250. Antijoin table 250 represents the results of an antijoin between table W 270 and table T 280 through the join condition w.a=t.a. Row 272 and row 274 are not reflected in antijoin table 250 because each meet the join condition with respect to a row in the table T 280. No row in table T 280 meets the join condition with respect to row 276, thus row 276 is reflected in antijoin table 250. Finally, row 278 is not reflected in the antijoin table 250 because when for a particular row, the left table column in the join condition (i.e. w.a) contains the NULL value, the row is not included in the results of the antijoin.
Because using the xe2x80x9cpreprocessedxe2x80x9d materialized data of a materialized view frequently saves the computer resources required to process queries, it is desirable to provide a method of satisfying an antijoin query from the materialized data of a materialized view that contains data that may be used to satisfy an antijoin query.
A method and apparatus for transforming queries is described. According to an aspect of the present invention, a select-project-join query Q that specifies an antijoin is rewritten into another query that references the materialized view M. The part of Q that is rewritten using M includes the tables being antijoined. Query Q can contain multiple joins and antijoins, as well as aggregates, distinct, and group by clauses. The invention transforms one-to-one and one-to-many lossless joins.